package com.itheima.demo03;

public class BlockSearchDemo01 {
    public static void main(String[] args) {
        //分块查找  就是创建索引表
        //1、定义数据
//        int[] arr = {16,5,9,12,21,18,32,23,37,26,45,34,50,48,61,52,73,66};//分块之前
        //如何分块，分几块？把数组的总长度开根号 就可得到大概分几块
        //需要把数据分块，规则块之间无序，块之内有序，且后一个块的最小值必须大于前一个块的最大值。
        int[] arr = {
                16,5,9,12,21,18,
                32,23,37,26,45,34,
                50,48,61,52,73,66
        };//分块之后

        Block b1 = new Block(21,0,5);
        Block b2 = new Block(45,6,11);
        Block b3 = new Block(73,12,17);

        Block[] blocks = {b1,b2,b3};

        //在去块对应的索引里面去查找对应的值的索引
        System.out.println(getIndex(blocks, arr, 37));
    }

    private static int getIndex(Block[] blocks,int[] arr,int number) {

        int blockIndex = findBlockIndex(blocks, number);
        if (blockIndex == -1){
            return -1;
        }
        //如果索引存在 就获取块的开始索引和结束索引在arr中查询number所在的索引位置 ，找到就返回索引值，未找到就返回-1
        int startIndex= blocks[blockIndex].getStartIndex();
        int endIndex= blocks[blockIndex].getEndIndex();

        for (int i = startIndex; i < endIndex; i++) {
            if (arr[i] == number){
                return i;
            }
        }

        return -1;
    }

    private static int findBlockIndex(Block[] blocks, int number) {
        //遍历判断要查询的值是在哪个块，并返回对应的块的索引
        for (int i = 0; i < blocks.length; i++) {
            if (blocks[i].getBlockMax() > number){
                return i;
            }
        }

        return -1;//未找到就返回 -1
    }

    //判断要查询的值是在哪个块

}

//创建块的类，用于记录每个块的最大值和开始、结束索引
class Block{
    private int blockMax;
    private int startIndex;
    private int endIndex;

    public Block() {
    }

    public Block(int blockMax, int startIndex, int endIndex) {
        this.blockMax = blockMax;
        this.startIndex = startIndex;
        this.endIndex = endIndex;
    }

    public int getBlockMax() {
        return blockMax;
    }

    public void setBlockMax(int blockMax) {
        this.blockMax = blockMax;
    }

    public int getStartIndex() {
        return startIndex;
    }

    public void setStartIndex(int startIndex) {
        this.startIndex = startIndex;
    }

    public int getEndIndex() {
        return endIndex;
    }

    public void setEndIndex(int endIndex) {
        this.endIndex = endIndex;
    }
}

